package main

import (
	"fmt"
	. "go_data_structures_and_algorithms/tool"
	"math"
	"time"
)

func main() {

	_, ints := LenRandomValueRandom(100, 10323)
	time.Sleep(10)
	fmt.Println(ints)
	RadixSort(ints) //开始排序
	fmt.Println(ints)

}

func RadixSort(arr []int) {
	if arr == nil || len(arr) < 2 { //判断如果数组为空或者数组长度为1就退出去
		return
	}

	beginToSort(arr, 0, len(arr)-1, findmaxDigit(arr)) //开始排序传入要排序的数组区间和最大值
	//最大值用来判断一共要排序几次因为排序是从个位开始排由个位上有序到最高位上有序所以找到最大值是很关键的一步
}

func findmaxDigit(arr []int) int {
	max := MinInt //给变量设置最小的值

	for _, v := range arr { //遍历数组然后找到比max大的就给他赋值肯定能找出最大值
		if max < v {
			max = v
		}
	}
	res := 0

	for max != 0 { //当max为0的话就默认0位不为0就进入for循环然后除以10个位数除以10后就为0res++结果就为1以此类推得出最大值有几位
		max /= 10
		res++
	}
	return res
}

func getDigit(num, n int) int { //num是要找的对应的数，n是要找的位数是第几位
	// 如果n小于等于0，返回0
	if n <= 0 { //如果要找的位数小于等于0那必定是0因为根本没有这种情况存在
		return 0
	}
	// 计算num的位数
	digits := int(math.Log10(float64(num))) + 1 //Math.log10(100000); // 5 这个Log10能输出这个数的位数如果要输出的位数大于当前这个数的位数也返回0
	// 如果n大于digits，返回0
	if n > digits {
		return 0
	}
	// 用除法和取余运算得到第n位数字
	return (num / int(math.Pow10(n-1))) % 10 //利用Pow10生成小一位的正整数然后让本体去除 再%10得出答案也就是
	// 比如123要输出其百位的数字也就是直接pow10(3-1) =100 123/100=1 再%10直接得出百位上的数字为1
}
func beginToSort(arr []int, L int, R int, digit int) {
	radix := 10                   //这个是本质上要准备多少个桶因为一般是十进制来进行计算和排序所以默认等于10十个桶默认是0-9
	help := make([]int, len(arr)) //创建一个跟原数组大小一样的辅助数组用来存放拍完序的内容

	for i := 1; i <= digit; i++ { //如果最大值是是四位数所以要从个位循环到万位所以要循环四次

		radixArr := make([]int, radix) //创建水桶数组，这个方法只需要一个水桶就能完成

		for ii := L; ii <= R; ii++ { //循环所有的数组内容

			radixArr[getDigit(arr[ii], i)]++ //找每个数组的当前位等于几就让对应的水桶上的位置上的数++
		}
		for j := 1; j < len(radixArr); j++ { //将水桶数组变成前缀和数组就知道当前位上以这个为结尾的数字最远可以放到数组的第几位

			radixArr[j] += radixArr[j-1]
		}

		for x := R; x >= L; x-- {
			i2 := getDigit(arr[x], i) //例如水桶数组的0索引位置上的值为2也就是说当前位上为0的数字有两个
			//他们最远可以排到2-1的位置也就是索引为1的地方
			//排完之后让水桶数组0索引位置上的值--
			//下次遇到当前位上为0的数字就从1-1的位置也就是放到辅助数组0位置上
			help[radixArr[i2]-1] = arr[x]
			radixArr[i2]--
		}
		for iii := 0; iii < len(arr); iii++ { //再将辅助数组赋值给arr后进行下一层循环
			arr[iii] = help[iii]
		}
	}
}
